import javax.xml.crypto.Data;
import java.util.Date;

/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/
//冒泡排序
public class BubbleSort {
    private BubbleSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //对于本身有序的数据，省去了多次的外层循环
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isSwaped = true;
                }
            }
            if (!isSwaped) {
                break;
            }
        }
    }

    public static <E extends Comparable<E>> void sort3(E[] arr) {
        for (int i = 0; i < arr.length - 1; ) {
            //最后一次交换的位置
            int lastSwappedIndex = 0;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    lastSwappedIndex = j + 1;
                }
            }
//            if (lastSwappedIndex == 0) {
//                break;
//            }
            i = arr.length - lastSwappedIndex;
        }
    }

    public static <E extends Comparable<E>> void sort4(E[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //arr[0,i)已排序
            for (int j = arr.length - 1; j > i; i--) {
                if (arr[j - 1].compareTo(arr[j]) > 0) {
                    swap(arr, j - 1, j);
                }
            }
        }
    }
}
